package com.salim.leetcode.$474;

import java.util.HashMap;

/**
 * 01背包
 * 核心思想是 当前元素这次要还是不要
 * 要就求解剩余元素的最大价值 不要就跳过
 * 我这里是做加法 实际应该做减法
 */
public class OnesAndZeroes {
    private String[] origin;
    private int targetZero = 0;
    private int targetOne = 0;
    private HashMap<String,Integer> loopBuffer = new HashMap<>();
    public int findMaxForm(String[] strs, int m, int n) {
        origin = strs;
        targetZero = m;
        targetOne = n;
        return loop(0,0,0);
    }

    public int loop(int start, int currentZero,int currentOne) {
        String key = start + "-" + currentZero + "-" + currentOne;

        if(loopBuffer.containsKey(key)){
            return loopBuffer.get(key);
        }
        if(start==origin.length){
            return 0;
        }

        int res;
        int zero=0;
        int one=0;
        for(int i =0;i<origin[start].length();i++){
            if(origin[start].charAt(i)=='0'){
                zero++;
            }else{
                one++;
            }
        }
        //如果没超过 分支成要 还是 不要
        //如果超过了 不要
        if(currentZero+zero<=targetZero && currentOne+one<=targetOne){
            res = Math.max(
                loop(start+1,currentZero,currentOne),
                1+loop(start+1,currentZero+zero,currentOne+one)
            );
        }else{
            res = loop(start+1,currentZero,currentOne);
        }

        loopBuffer.put(key,res);
        return res;
    }

//    public static void main(String[] args){
//        OnesAndZeroes onesAndZeroes = new OnesAndZeroes();
//        String[] strs = {"10","0001","111001","1","0"};
//        int m = 5;
//        int n = 4;
//        System.out.println(onesAndZeroes.findMaxForm(strs,m,n));
////        String[] strs2 = {"011111","001","001"};
////        System.out.println(onesAndZeroes.findMaxForm(strs2,4,5));
//    }

}
